package com.computer.fundamentals.algorithm;

import com.computer.util.UniversalMethod;

/**
 * 背包问题假设：
 * 1. 我们有n种物品，物品j的重量为wj，价格为pj。
 * 2. 我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。
 * 3. 如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题；如果不限定物品的选择数量，则问题称为完全背包问题
 */
public class KnapsackProblem {

    /**
     * 0-1背包解决方案
     * 题目如下：
     * ------------------------------------------------------------------------------------------------------------
     * 有N件物品和一个容量为V的背包，第i件物品的重量是w[i],价值是v[i]。
     * 求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
     * ------------------------------------------------------------------------------------------------------------
     */
    public int zeroOneKnapsackProblem(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity+1];
        for (int i = 1;i < weights.length;i++) {
            int weight = weights[i];
            int value = values[i];
            for (int j = capacity;j >= weight;j--) {
                dp[j] = Math.max(dp[j], dp[j - weight] + value);
            }
        }

        return dp[capacity];
    }

    /**
     * 完全背包解决方案
     * 题目如下：
     * 有N种物品和一个容量为V的背包，每种物品都有无限件可用。
     * 第i种物品的重量是c，价值是w。将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
     */
    public int piggyBank(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity+1];
        for (int i = 1;i < weights.length;i++) {
            int weight = weights[i];
            int value = values[i];
            for (int j = weight;j <= capacity;j++) {
                dp[j] = Math.max(dp[j], dp[j - weight] + value);
            }
        }

        return dp[capacity];
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        KnapsackProblem knapsackProblem = new KnapsackProblem();
        UniversalMethod.Knapsack knapsack = UniversalMethod.createKnapsack();

        System.out.println("------------物品重量------------");
        UniversalMethod.printArray(knapsack.weights);
        System.out.println("\n------------物品价值------------");
        UniversalMethod.printArray(knapsack.values);
        System.out.println("\n------------背包容积------------");
        System.out.println(knapsack.capacity);
        System.out.println("\n");

        System.out.println("------------0-1背包测试------------");
        int zeroOneMaxValue = knapsackProblem.zeroOneKnapsackProblem(knapsack.weights, knapsack.values, knapsack.capacity);
        System.out.println(zeroOneMaxValue);
        System.out.println("\n");

        System.out.println("------------0-1背包测试------------");
        int piggyBankMaxValue = knapsackProblem.piggyBank(knapsack.weights, knapsack.values, knapsack.capacity);
        System.out.println(piggyBankMaxValue);
        System.out.println("\n");

    }
}